#!/usr/bin/perl
# Coded for sigMatch
# Author: Ramakrishnan Kandhan (ramak@cs.wisc.edu)
#
# ====================================================================
# The Apache Software License, Version 1.1
#
# Copyright (c) 2000 The Apache Software Foundation.  All rights
# reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in
#    the documentation and/or other materials provided with the
#    distribution.
#
# 3. The end-user documentation included with the redistribution,
#    if any, must include the following acknowledgment:
#       "This product includes software developed by the
#        Apache Software Foundation (http://www.apache.org/)."
#    Alternately, this acknowledgment may appear in the software itself,
#    if and wherever such third-party acknowledgments normally appear.
#
# 4. The names "Apache" and "Apache Software Foundation" must
#    not be used to endorse or promote products derived from this
#    software without prior written permission. For written
#    permission, please contact apache@apache.org.
#
# 5. Products derived from this software may not be called "Apache",
#    nor may "Apache" appear in their name, without prior written
#    permission of the Apache Software Foundation.
#
# THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
# ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
# ====================================================================
#
# This software consists of voluntary contributions made by many
# individuals on behalf of the Apache Software Foundation.  For more
# information on the Apache Software Foundation, please see
# <http://www.apache.org/>.
#
# Portions of this software are based upon public domain software
# originally written at the National Center for Supercomputing Applications,
# University of Illinois, Urbana-Champaign.
#

# Get the uniq set of q-grams which encompass
# the entire signature set
#
# Usage: ./b-gram_cover <Sig File> <beta> <gamma> <b-gram File> <special signatures>

use strict;

#input params
my $sigF = shift;

#initialize the parameters
my $lengthb = 4;
my $beta = shift; 
my $num_hash = 1;
my $MaxLLSize = 10;
my $MaxHashSize = 200;
my $fminl = $lengthb + $beta + $num_hash - 1;
my $arrsize = 16**$lengthb;
my $number = shift;

#Initialize the char array
my @c;
@c = ('0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f');


#initialize the string array
my @str;
for (my $j=0; $j<=$#c; $j++) {
	for (my $k=0; $k<=$#c; $k++) {
		for (my $m=0; $m<=$#c; $m++) {
			for (my $n=0; $n<=$#c; $n++) {
				$str[16*16*16*$j+16*16*$k+16*$m+$n] = "$c[$j]$c[$k]$c[$m]$c[$n]";
			}
		}
	}
}


#open the signatures file
open my $fd,$sigF;
my @lines = <$fd>;
close $fd;
chomp(@lines);


#separate the polymorphic and non-polymorphic signatures
my @psign;
my @npsign;
my $pscount = 0;
my $npscount = 0;
foreach my $li (@lines) {
	my @l = split(/=/,$li);            #这个涉及到特征码格式的问题
	if ($l[0] =~ m/\*|\?|\(|\||\)|\{|\}/) {
		$psign[$pscount++] = $l[1];
	}
	else {
		$npsign[$npscount++] = $l[1];
	}
}



#first find the length of the smallest and
#largest non-polymorphic signatures
my $maxlength = 0;
my $minlength = length($npsign[0]);
foreach my $nps (@npsign) {
	if (length($nps) > $maxlength) {
		$maxlength = length($nps);
	}
	if (length($nps) < $minlength) {
		$minlength = length($nps);
	}
}


#find max nps stretch in each ps
my @maxarr;
foreach my $ps (@psign) {
	my $okflag = 0;
	my @parr = split(/\*|\?|\(|\||\)|\{|\}/,$ps);
	my $maxl = 0;
	foreach my $p (@parr) {
		#find max np stretch of a particular ps 
		if (length($p) > $maxl) {
			$maxl = length($p);
		}
	}
	push (@maxarr,$maxl);
}


#find min of max nps streches
my $minl = $maxarr[0];
foreach my $mx (@maxarr) {
	if ($mx < $minl) {
		$minl = $mx;
	}
}


#Create a sorted array for np streches
my @npstretch;
my @npsc;
my @spstr;
my $escChar ="z";
foreach my $ps (@psign) {
	my $flag = 0;
	my @parr = split(/\*|\?|\(|\||\)|\{|\}/,$ps);
	my @sparr = sort { length($b) <=> length($a) } @parr;
	my $pushstr;
	foreach my $sp(@sparr) {
		if (length($sp) > $fminl) {
			$pushstr = "$pushstr$sp$escChar";
			$flag = 1;
		}
		#push (@npstretch,$sp);
	}
	#push (@npsc,$#sparr+1);
	if ($flag == 1) {
		push (@npsign,$pushstr);
	}
	else {
		push (@spstr,$ps);
	}
}


#Now find the minimal set for psigns
my @acount;
for (my $i=0; $i < $arrsize; $i++) {
	$acount[$i] = 0;
}


for (my $j=0; $j <= $#npsign; $j++) {

	for (my $k=0; $k< length($npsign[$j])-4; $k++)	{    #这里修改过，$k必须加2，因为一个字符为一个字节=2位16进制
		my $str = substr ($npsign[$j], $k, 4);
		if ($str =~ m/^20/ || $str =~m/20$/) { next; }
		if ($str =~ m/^00/ || $str =~m/00$/) { next; }
		if ($str =~ m/^30/ || $str =~m/30$/) { next; }
		if ($str =~ m/^01/ || $str =~m/01$/) { next; }
		if ($j <= $npscount) {
			if (index($npsign[$j], $str) != $k) { next;}
			if (length($npsign[$j]) - index($npsign[$j],$str) > $fminl) {
				my $ind = eval "0x$str";
				$acount[$ind]++;
			}
		}
		else {
			my @npsarr = split (/$escChar/,$npsign[$j]);
			foreach my $npsa (@npsarr) {
				if ($npsa =~ m/\Q$str\E/) {
					if (length($npsa) - index($npsa,$str) > $fminl) {
						my $ind = eval "0x$str";
						$acount[$ind]++;
					}
				}
			}
		}
	}
}

open my $fd, ">tmp.txt";
for (my $i=0; $i < $arrsize; $i++) {
	my $str = sprintf("%.4x", $i);
	print $fd "$acount[$i] $str\n";
}
close $fd;

system ("cp tmp.txt $sigF.counts");
system ("sort -nr tmp.txt > tmp1.txt");

open my $fd, "tmp1.txt";
my @temp = <$fd>;               #temp数组里面存储的是b-gram的频率
close $fd;
chomp(@temp);

#system ("rm -f tmp1.txt");
#system ("rm -f tmp.txt");

my @found;
for (my $j=0; $j <= $#npsign; $j++) {
	$found[$j] = $number;                  
}

my @flist;
foreach my $t (@temp) {
	my @tarr = split (/ /,$t);                 #从最高频率的str开始
	my $str = $tarr[$#tarr];
	if ($str =~ m/^20/ || $str =~m/20$/) { next; }
	if ($str =~ m/^00/ || $str =~m/00$/) { next; }
	if ($str =~ m/^30/ || $str =~m/30$/) { next; }
	if ($str =~ m/^01/ || $str =~m/01$/) { next; }

	my $flag = 0;
	for (my $j=0; $j <= $#npsign; $j++) {
		if ($found[$j] != 0) {
			my $str = $tarr[$#tarr];
			if ($npsign[$j] =~ m/$str/) {
				if ($j <= $npscount) {
					if (length($npsign[$j]) - index($npsign[$j],$str) > $fminl) {
						$found[$j]--;
						$flag = 1;
					}
				}
				else {
					my @npsarr = split(/$escChar/, $npsign[$j]);
					foreach my $npsa(@npsarr) {
						if ($npsa =~ m/$str/) {
							if (length($npsa) - index($npsa,$str)) {
								$found[$j]--;
								$flag = 1;
								last;
							}
						}
					}
				}
			}
		}
	}
	if ($flag == 1) {
		push (@flist, $tarr[$#tarr]);
	}
}

print "@flist\n";                
my @ocs;

my @found;                                
for (my $j=0; $j <= $#npsign; $j++) {
	$found[$j] = $number;                    
}

for (my $m=$#flist; $m>=0; $m--) {    #修改成了m>=0;
	my $str = $flist[$m];
	my $flag = 0;
	for (my $j=0; $j <= $#npsign; $j++) {
		if ($found[$j] != 0) {
			if ($npsign[$j] =~ m/$str/) {
				if ($j <= $npscount) {
					if (length($npsign[$j]) - index($npsign[$j],$str) > $fminl) {
						$found[$j]--;
						$flag = 1;
					}
                                        
				}
				else {
					my @npsarr = split(/$escChar/, $npsign[my $j]);
					foreach my $npsa(@npsarr) {
						if ($npsa =~ m/$str/) {
							if (length($npsa) - index($npsa,$str)) {
								$found[$j]--;
								$flag = 1;
								last;
							}
						}
					}
                                       
				}
			}
                   
		}
             
	}
	if ($flag == 1) {
		push (@ocs, $str);
	}
}

print "ocs=@ocs\n";        

my $nf = 0;
for (my $j=0; $j <= $#npsign; $j++) {
	if ($found[$j] == $number)
	{
		$nf++;
	}
}

my $outF = shift;
open my $fd, ">>$outF";
for (my $i=0; $i<=$#ocs; $i++) {
	print $fd "$ocs[$i]\n";
}
close $fd;

my $spF = shift;
open my $fd, ">>$spF";
for (my $i=0; $i<=$#spstr; $i++) {
	print $fd "$spstr[$i]\n";
}
close $fd;
